Pascals triangle

Time: O(N^2); Space: O(1); easy

Given numRows, generate the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it.

Example 1:

Input: numRows = 5

Output:

[
        [1],
       [1,1],
      [1,2,1],
     [1,3,3,1],
    [1,4,6,4,1]
]

1. Dynamic Programming

Intuition If we have the a row of Pascal’s triangle, we can easily compute the next row by each pair of adjacent values.

Algorithm Although the algorithm is very simple, the iterative approach to constructing Pascal’s triangle can be classified as dynamic programming because we construct each row based on the previous row.

First, we generate the overall triangle list, which will store each row as a sublist. Then, we check for the special case of 00, as we would otherwise return [1]. If numRows > 0, then we initialize triangle with [1] as its first row.

[17]:

class Solution1(object):
    """
    Time: O(numRows^2)
    Space: O(numRows^2)
    """
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        result = []

        for row_num in range(numRows):
            # The first and last row elements are always 1.
            row = [None for _ in range(row_num + 1)]
            row[0], row[-1] = 1, 1

            # Each triangle element is equal to the sum of the elements
            # above-and-to-the-left and above-and-to-the-right.
            for j in range(1, len(row)-1):
                row[j] = result[row_num-1][j-1] + result[row_num-1][j]

            result.append(row)

        return result

[18]:

s = Solution1()
numRows = 5
assert s.generate(numRows) == [
        [1],
       [1,1],
      [1,2,1],
     [1,3,3,1],
    [1,4,6,4,1]
]

[19]:

class Solution2(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        result = []
        for i in range(numRows):
            result.append([])
            for j in range(i + 1):
                if j in (0, i):
                    result[i].append(1)
                else:
                    result[i].append(result[i - 1][j - 1] + result[i - 1][j])
        return result

[20]:

s = Solution2()
numRows = 5
assert s.generate(numRows) == [
        [1],
       [1,1],
      [1,2,1],
     [1,3,3,1],
    [1,4,6,4,1]
]

[21]:

class Solution3(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        if not numRows: return []
        res = [[1]]
        for i in range(1, numRows):
            res.append(list(map(lambda x, y: x + y, res[-1] + [0], [0] + res[-1])))
        return res[:numRows]

[22]:

s = Solution3()
numRows = 5
assert s.generate(numRows) == [
        [1],
       [1,1],
      [1,2,1],
     [1,3,3,1],
    [1,4,6,4,1]
]

[23]:

class Solution4(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        if numRows == 0: return []
        if numRows == 1: return [[1]]
        res = [[1], [1, 1]]

        def add(nums):
            res = nums[:1]
            for i, j in enumerate(nums):
                if i < len(nums) - 1:
                    res += [nums[i] + nums[i + 1]]
            res += nums[:1]
            return res

        while len(res) < numRows:
            res.extend([add(res[-1])])
        return res

[24]:

s = Solution4()
numRows = 5
assert s.generate(numRows) == [
        [1],
       [1,1],
      [1,2,1],
     [1,3,3,1],
    [1,4,6,4,1]
]